{
 "nbformat": 4,
 "nbformat_minor": 0,
 "metadata": {
  "colab": {
   "name": "Second Partial (Solved).ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "f5X9iaV2tFbX"
   },
   "source": [
    "# Planet Express Deliveries\n",
    "## Problem definition\n",
    "Planet Express deliveries wants to optimize their transportation network from a set of source warehouses to a set of destinations. In particular, they want to minimize the transportation costs through a set of intermediate warehouses, so that items are transported from the source warehouses, through the intermediate warehouses, to the destination regions.\n",
    "\n",
    "Let us first consider that transportation costs per item from the source warehouse $i$ to intermediate warehouse $j$ as $s_{ij}$ and that the transportation costs per item from intermediate warehouse $j$ to destination region $k$ is $t_{jk}$. Let us note the capacity of source warehouses as $a_{i}$ items, the capacity of intermediate warehouses $j$ as $b_j$ items, and the demand for region $k$ as $d_k$ items. Let us also consider that $m$ is the number of source warehouses, $n$ is the number of intermediate warehouses and $p$ is the number of destination regions.\n",
    "\n",
    "**a** Consider that m = p = 3 and n = 5 and draw a network to solve the transportation problem as a maximal flow at minimum cost problem. \n",
    "\n",
    "The network consists of a Source Node, 3 nodes that represent the source warehouses, 5 nodes that represent the intermediate warehouses, and 3 nodes that represent the destination regions. The edges must be labeled with the capacities and the costs. In the figure below, capacities and costs of every edge are labeled as \"capacity, cost\", e.g. an edge with capacity $a_{11}$ and cost $s_{11}$ is labeled as $a_{11}, s_{11}$. For the sake of clarity, only the first and last edges are labeled at every stage:\n",
    "\n",
    "![graph network](img/planet_express.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "XaOurAD9ZAQx"
   },
   "source": [
    "**b** Model the problem as a Mixed Integer Programming (MIP), not taking into account the values of m,p, and n defined in the previous section"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "R_bTVlnaZiyo"
   },
   "source": [
    "**Decision variables**\n",
    "\n",
    "- $x_{ij}$: (Integer) Number of units to transport from source warehouse i to intermediate warehouse j\n",
    "\n",
    "- $y_{jk}$: (Integer) Number of units to transport from intermediate warehouse j to destination region k\n",
    "\n",
    "The linear model is then: \n",
    "\n",
    "$\\min z = \\sum_i\\sum_js_{ij}*x_{ij} + \\sum_j\\sum_kt_{jk}*y_{jk}$\n",
    "\n",
    "$s.t.$\n",
    "\n",
    "Source warehouse capacity constraints: \n",
    "\n",
    "$\\sum_jx_{ij} \\leq a_i \\quad \\forall i$\n",
    "\n",
    "Intermediate warehouse capacity constraints:\n",
    "\n",
    "$\\sum_ky_{jk} \\leq b_j \\quad \\forall j$\n",
    "\n",
    "Demand constraints: \n",
    "\n",
    "$\\sum_jy_{jk} \\geq d_k \\quad \\forall k$\n",
    "\n",
    "Flow constraints:\n",
    "\n",
    "$\\sum_ix_{ij} = \\sum_ky_{jk} \\quad \\forall j$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "E6vJoHHCZjeI"
   },
   "source": [
    "**c** Planet Express is now considering the use of warehouses from an external provider. The provider of the service has a total of $n_e$ external warehouses. They offer a fixed cost $F_l$ when an external warehouse $l$ is used, plus a cost per item received and processed in warehouse $l$, $r_l$. External warehouse $l$ has a capacity of $c_l$ items. Modify your model to incorporate this offer into your distribution network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "FyYgxYtJiIu0"
   },
   "source": [
    "The following decision variables are introduced in the model: \n",
    "\n",
    "- $Y_l$: (Binary) Indicates if external warehouse $l$ is used\n",
    "- $x'_{il}$: (Integer) Number of units to transport from source warehouse i to external intermediate warehouse l\n",
    "\n",
    "- $y'_{lk}$: (Integer) Number of units to transport from external intermediate warehouse l to destination region k\n",
    "\n",
    "The model is now:\n",
    "\n",
    "$\\min z = \\sum_i\\sum_js_{ij}*x_{ij} + \\sum_j\\sum_kt_{jk}*y_{jk} + \\sum_lY_l*F_l + \\sum_i\\sum_lr_l*x'_{il}$\n",
    "\n",
    "$s.t.$\n",
    "\n",
    "Source warehouse capacity constraints: \n",
    "\n",
    "$\\sum_jx_{ij}+\\sum_lx'_{il} \\leq a_i \\quad \\forall i$\n",
    "\n",
    "Intermediate warehouse capacity constraints:\n",
    "\n",
    "$\\sum_ky_{jk} \\leq b_j \\quad \\forall j$\n",
    "\n",
    "External warehouse capacity constraints:\n",
    "\n",
    "$\\sum_ix'_{il} \\leq c_l \\quad \\forall l$\n",
    "\n",
    "Demand constraints:\n",
    "\n",
    "$\\sum_jt_{jk} + \\sum_lt'_{lk} \\geq d_k \\quad \\forall k$\n",
    "\n",
    "Flow constraints:\n",
    "\n",
    "$\\sum_ix_{ij} = \\sum_ky_{jk} \\quad \\forall j$\n",
    "\n",
    "$\\sum_ix'_{il} = \\sum_ky'_{lk} \\quad \\forall l$\n",
    "\n",
    "Logical constraint:\n",
    "\n",
    "$\\sum_ix'_{il} \\leq M*\\sum_lY_l$\n"
   ]
  }
 ]
}